The present invention relates to a method for analyzing and ordering informational data representing the physical characteristics of an object. More specifically, the invention relates to the generation of ordered point cloud information from layered input data and the output of a surface-based object representation.
Various apparatus and methods exist in the art for reverse engineering an existing product in order to determine its structure and makeup. Such a reverse engineering process may be desirable because a computer aided design file representing the object does not exist, because a mold for the object does not exist, or simply because the part has been modified independently of the existing rebuilt materials.
It is often desirable to know the geometry, both external and internal, of existing objects. Various apparatus for the delamination of such objects are known in the art. For example, such an apparatus and method for creating three-dimensional modeling data from an object is disclosed in U.S. Pat. No. 5,621,648, to Crump, which is hereby incorporated by reference in its entirety. The ""648 patent discusses and discloses the delamination of an object encased in an encasing material by successively cutting off layers of the encased object, imaging the exposed surfaces and producing a surface model by lofting surfaces on a stack of generated spline art layers. Such a method and apparatus allows the object to be examined for both external and internal geometry.
Other methods and apparatus for traditional measuring of dimensions and generation of surfaces involve extensive use of a probe and metering technique by which a physical probe is placed at numerous and various points on an object, making measurements of the relative location at each touching point. Such a process is tedious and is subject to the human error of misplacing the probe or failing to recognize important changes in geometry of a system. Even if such a probe and meter system were automated, the time consumed by such a system would be immense due to the large numbers of points to be probed. Further, such a probe and metering technique does not capture internal geometry well, especially internal geometry with no external availability. Such geometry will not be captured by a probe and meter technique.
Delaminating systems and other systems which generate or provide physical characteristic data of various objects, such as magnetic resonance imaging (MRI), X-ray technology and the like, use a wide variety of output file formats and output protocols to transmit raw data information pertaining to the object to a computer aided design tool or other computer system for construction of a three-dimensional image representative of the object. Many such systems export a continuous stream of data, and many surfacing computer programs, commonly used to work with such data sets require input of all data at one time. The vast amount of data generated by such a process requires a great deal of storage space and computer power in order to be able to work with it. Too much data leads to an unwieldy process. Working with a full data set of information creates numerous problems with the usefulness of such data.
The delaminating machine disclosed in the ""648 patent and other object representation technologies can provide data generated layer by layer. When working with layered data, smaller amounts of information are used at one specific time, reducing the time and storage requirements for image and object reconstruction. It would be desirable to be able to use layer by layer data from a delamination or other imaging system to construct a computer aided design image or specific output file format which is more usable because it has a reduced size without sacrificing informational content.
A further problem with other systems or methods for generating three-dimensional output data lies in their inability to appropriately and accurately distinguish between internal and external geometry configurations. Capturing a complete data set incorporating all the geometry of an object has several requirements, including the gathering of enough data points to define a surface, and measurement and sensing capable of providing data representative of all surfaces. If the surface to be analyzed or reconstructed is obstructed, such as an internal surface or the inside of a specific part, important geometry will be difficult or impossible to measure or photograph, and will be especially difficult to distinguish using probe and meter techniques. Further, a method is required to distinguish between external and internal geometries to be able to accurately generate surface representations. A system such as that disclosed in the ""648 patent provides data representative of all internal and external geometry. However, once complete internal and external geometry representations have been captured, or generated, the amount of data required to accurately represent such surfaces can be extreme given the resolution of the generated representations. It would be desirable to provide a method which could accurately and appropriately distinguish between internal and external geometry points.
When layer by layer data is sent in such a layered order to a software program or integrated hardware and software system for generation of an output file, it may take many formats. For example, in the ""648 patent, each scanned surface layer will typically contain a series of pixels of either black or white, with one color representing encasing material, and the other pixel color representing the object. Other imaging technologies may also provide layered data representative of object and non-object pixels. It would be desirable to provide a method of taking data representations of this type and for processing them to produce a three-dimensional surface representation while reducing the amount of information without reducing the quality of the final generated image.
Layer by layer data will contain certain object geometries which may be difficult to recognize. Such geometries include the first or last layer, referred to as a cap, on which a geometry appears. This may be an external geometry or an internal geometry. Also, at certain levels or layers throughout an object, especially a complex object, geometries may split. For example, on one layer there may be one section of a whole, and on the next, there may be two sections of the same whole that have split from the first section of the whole. A table fork for example splits from the handle to a series of tines. It has been difficult for prior art methods to distinguish a split, or conversely, a join, in layer by layer geometry. It would, therefore, be desirable to provide a method by which caps, splits, and joins are recognized and accurately dealt with. It would also be desirable to provide a method which would convert layer by layer pixel data to point data which may be more suitably used by a data processor such as a computer and associated software.
It is an object of the present invention to provide a method for generating ordered point cloud information based on layer by layer data.
It is another object of the present invention to improve a method for recognition and treatment of caps, splits, and joins in three dimensional object representation data.
It is still another object of the present invention to provide a method for selective sampling of points and layers in a layer by layer representation of a three-dimensional object.
It is yet another object of the present invention to provide a method for generation of three-dimensional surface representations of an object by stitching layered point clouds together to form a series of facets.
The present invention achieves the preceding objects and overcomes the problems of the prior art by providing a method of analyzing, refining and working with layer by layer pixel data information generated by a delaminating machine or the like to provide an output format representative of a three dimensional surface.
The preferred method of the present invention comprises the generation of layer by layer ordered point clouds which define both the internal and external geometry of the object being analyzed, and the stitching together of the layered point clouds to form a surface representation of the object. The data is typically presented from a delaminating machine or the like, in which a two dimensional pixel grid will be defined in which a pixel of one color defines areas of the grid which represent object material, and pixel of a different color defines the areas of the grid which represent non-object material. Typically, these pixels are black and white. Each layer of pixel information is converted from this pixel representation to a point cloud representation.
The point cloud representation is generated by assigning points representing the surfaces of the object, both external and internal, to object/non-object interfaces, and by ordering the points on the basis of the color of the pixel immediately underneath the point. By the term xe2x80x9cunderneath the pointxe2x80x9d, it is meant that if the grid were assigned horizontal X coordinates and vertical Y coordinates beginning at the upper left, the pixel underneath a point will be that pixel having the same X value, with a Y value one unit higher. It should be understood that the designation xe2x80x9cunderneathxe2x80x9d may appropriately be changed to accommodate various scanning methods, although the designation described is used for the scanning method described below herein.
When the first point of a new point cloud, which is a series of ordered points, is found in a scanning routine, the point will, because of the nature of the scanning routine, either be an external geometry point or an internal geometry point, depending respectively upon whether the pixel underneath the point is an object pixel or a non-object pixel. Once a first point is found, the method of the present invention will search for the second point, which will be an immediately adjacent point one unit away from the first point. A unit is defined as the gap between a point found and the next point which could be assigned along the surface represented by an interconnection of the surface points. When a point is assigned to a point cloud, it is removed from further consideration for addition to the same or a different cloud. When the method of the present invention finds no subsequent point one unit away from the point being considered, it assumes closure of the current point cloud by verifying that the distance between the final point and the first point of the cloud is one unit. In this manner, all point clouds on a layer are ordered. In turn, all layers of the object layer by layer pixel representation are converted to point cloud data information.
Once point clouds are generated for each layer of the layer by layer pixel data, successive layers of point clouds are stitched together by the method of the present invention to form a surface representation of the complete geometry of the object, both external and internal. The distance between point clouds on successive layers, referred to as neighbor clouds, is measured. A neighbor point cloud to the cloud currently under consideration is defined as the point cloud on an immediately adjacent layer that is closest to the point cloud being considered on the existing layer. Closest is defined as the distance from each point on the current cloud to the closest point of the cloud on the adjacent layer. Most clouds have one neighbor cloud. However, in the case of a bifurcation or joining such as will be described in greater detail below, a cloud may have two or more neighbor clouds.
Once neighbor clouds are defined, the distance between each point of a cloud and the points on its neighbor clouds is determined. The two points on neighbor clouds which are closest to each other, of the points of the two neighbor clouds, are connected together. Following this, each subsequent point later in the order of the cloud is also connected to the point on the neighboring cloud closest to it provided that no points on either cloud are skipped, and that no point is connected to a point behind its current order in the clouds. In other words, the method looks for the closest point to the current point which is on the adjacent cloud, moving forward in the point order of the clouds. Once all points of the neighboring clouds have been stitched together, further connections are added between points on adjacent clouds, and between adjacent points in the cloud, so that each point on each cloud is part of a defined triangle when the points of the clouds are also connected in order.
This series of triangles connecting adjacent layers of the object provides a definition of a surface, with the faces of the triangles forming a surface representation of the object. This surface representation of the object may be generated in a variety of formats. A common format for such a representation is stereolethography tessellation language (STL).
Further methods of the present invention involve isolating the specific layer containing information of the object to be represented, distinguishing between multiple objects to be analyzed in the same encased area provided they do not touch, and specific or method specific sampling techniques to remove or add points within a cloud, entire clouds, or even entire layers to reduce or increase the quantity and/or quality of data required for an accurate representation of the object, while maintaining the integrity and accuracy of the representation.
The method of the present invention also may be used in cropping a set of data. In the isolation or monolith step, the outer boundaries of the object are determined. Once the outer boundaries are known, the method can eliminate layers or portions of layers which do not contain parts of the object. This optional method step may be referred to as cropping.
Some machines or other data generation apparatus may generate data already in point format. The method of the present invention is readily adaptable to utilization with such data, by eliminating the step of conversion of layer by layer pixel data to point data.
The foregoing objects of the present invention will become apparent to those skilled in the art when the following detailed description of the invention is read in conjunction with the accompanying drawings and claims, with like numerals in the drawings referring to similar or identical parts throughout.